package graph.search;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Dijkstra {

	public static ArrayList<Node> listN = new ArrayList<Node>();
	public static ArrayList<Node> listVisited = new ArrayList<Node>();
	public static Node rootNode;

	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {

		LoadDataTung("/home/quyet/test/sharedQuyet/01id1500.txt");
		for (int i = 1775; i < 1775 + listN.size(); i++) {
			// listVisited = new ArrayList<Node>();
			int id = listN.indexOf(new Node(i+""));
			if (id >= 0) {
				rootNode = listN.get(id);
				// Run DFS
				Run();

				for (Node n : listN) {
					if (n.minDistance != Integer.MAX_VALUE && n.minDistance > 3) {
						System.out.println(i + "->" + n.id + " : "
								+ n.minDistance);
					}
				}
			}
		}
	}

	public static void Run() {

		Queue<Node> q = new LinkedList<Node>();

		for (Node n : listN)
			n.minDistance = Integer.MAX_VALUE;

		rootNode.minDistance = 0;
		q.add(rootNode);

		while (!q.isEmpty()) {
			Node u = q.poll();
			for (Node e : u.children) {
				int newDist = u.minDistance + 1;
				if (newDist < e.minDistance) {
					e.minDistance = newDist;
					q.add(e);
				}
			}
		}
	}

	public static void LoadData(String filePath) throws IOException {
		FileReader f = new FileReader(filePath);
		BufferedReader bNode = new BufferedReader(f);

		String strLine = null;
		while ((strLine = bNode.readLine()) != null) {
			String[] node = strLine.split("\t");

			Node ni = new Node(node[0]);
			for (int i = 3; i < node.length; i++) {
				Node nj = new Node(node[i]);
				ni.children.add(nj);
				if (!listN.contains(nj))
					listN.add(nj);
			}

			if (!listN.contains(ni))
				listN.add(ni);
			else {
				if (ni.children.size() > 0) {
					int id = listN.indexOf(ni);
					listN.get(id).children = ni.children;
				}
			}
		}
		bNode.close();
	}

	public static void LoadDataTung(String filePath) throws IOException {
		FileReader f = new FileReader(filePath);
		BufferedReader bNode = new BufferedReader(f);

		String strLine = null;
		while ((strLine = bNode.readLine()) != null) {
			String[] node = strLine.split("\t");

			Node ni = new Node(node[0]);
			for (int i = 9; i < node.length; i++) {
				Node nj = new Node(node[i]);
				ni.children.add(nj);
				if (!listN.contains(nj))
					listN.add(nj);
			}

			if (!listN.contains(ni))
				listN.add(ni);
			else {
				if (ni.children.size() > 0) {
					int id = listN.indexOf(ni);
					listN.get(id).children = ni.children;
				}
			}
		}
		bNode.close();
	}
}
